1. Field of the Invention
The present invention relates to digital image compression techniques in general, and, in particular, to hardware for performing embedded block coding in a JPEG2000 codec.
2. Description of the Related Art
With the expansion of the Internet as well as the explosive growth of digital storage devices, the use of compression techniques for storing and transporting multimedia content is becoming increasingly important. One multimedia compression protocol is JPEG (Joint Photographic Experts Group) which is used for storing still photographs or images. The original JPEG standard was created in the late 1980s and has become widely used on the Internet as well as in digital imaging equipment. In 1997, a call for proposals for the next generation JPEG standard, called JPEG2000, was issued by the International Organization for Standardization (ISO), under whose aegis the original JPEG standard was promulgated. The first part of the draft standard (ISO/IEC 15444-1: JPEG2000 image coding system) was released in 2000.
JPEG2000 supports both lossy and lossless compression of single-component (e.g., greyscale) and multi-component (e.g., color) imagery. In addition to this basic compression functionality, other features are provided, including 1) progressive recovery of an image by fidelity or resolution; 2) region-of-interest coding, whereby different parts of an image may be coded with differing fidelity or resolution; 3) random access to specific regions of an image without needing to decode the entire codestream; 4) flexible file format; and 5) good error resilience. Due to its improved coding performance and many attractive features, there is a very large potential application base for JPEG2000. Some potential application areas include: image archiving, web browsing, document imaging, digital photography, medical imagery, and remote sensing.
As shown in FIG. 1, the JPEG2000 encoding process can be broken down into various steps. In the DC Level Shifting step 110, DC level shifting and, optionally, a forward component transform is performed on tiles of the original image. Any still image may be divided into tiles, which are rectangular arrays that include the same relative portion of the components that make up the image. In the DWT step 120, the tile components are decomposed using a Discrete Wavelet Transform (DWT), thus producing wavelet coefficients. The use of DWT provides the multi-resolution capabilities of JPEG2000. As shown in FIG. 2, a first DWT stage decomposes the original image (LL0) into four sub-bands, denoted by the labels LL1, HL1, LH1, and HH1. The labels indicate the filtering and decomposition level (LL1=low-pass filtering horizontally, low-pass filtering vertically, at the 1st level of decomposition). These sub-bands are populated with wavelet coefficients that describe spatial frequency characteristics of the original image. The second stage further breaks down LL1 into the four sub-bands LL2, HL2, LH2, and HH2. Although only three such stages are shown in FIG. 2, this process may continue for many stages. Each LLn sub-band is a reasonable low resolution rendition of LLn−1 with half the width and height.
Returning to FIG. 1, each sub-band, comprised of coefficients produced in the DWT step, is subjected to uniform scalar quantization in the Quantization step 130. This step may be used to further compress the data stream by selecting a large quantization step size. However, the JPEG2000 standard does not require any particular method to select a step size, and each sub-band is allowed its own step size. Next, the quantized coefficients of the sub-bands are further broken down into two-dimensional arrays (e.g., 64×64 or 32×32 samples) called code-blocks. In the Block Coding, or Coefficient Bit Modeling, step 140, the code-blocks are coded with three coding passes, described below. Each of these coding passes collects contextual information about the bits in the coefficients of the code-blocks, and results in the generation of a coefficient vector for each coefficient in the code-block. The Arithmetic Coding step 150 uses the context vectors and the corresponding coefficients to create a compressed datastream, which may be interleaved in the Data Ordering step 160.
Because the present invention concerns the Block Coding, or Coefficient Bit Modeling, step 140, a more detailed description of that step will be made with reference to FIGS. 3 and 4. As stated above, the code-blocks of quantized coefficients are coded with three coding passes. These coding passes are performed on “bitplanes”, each of which is an array consisting of bits taken from the same position in each coefficient. The first bitplane is comprised of the most significant bits (MSB) of all the coefficient magnitudes in the code-block. The second bit-plane is comprised of the second MSBs of all the coefficient magnitudes in the code-block, and so on. FIG. 3 shows a code-block of quantized coefficients, where each quantized coefficient has four bits (e.g., a1 a2 a3 a4) and the MSB of each coefficient has a subscript of “1” (e.g., a1). The first bitplane is comprised of a1, b1, c1, d1, etc., the second bit-plane is comprised of a2, b2, c2d2, etc.
The number of bit-planes in a code-block that are identically zero is signaled as side information, and not encoded. Starting from the first bitplane having a single 1, each bitplane is encoded in three passes (referred to as sub-bitplanes). The three passes of the bit-planes are scanned in a particular pattern. Namely, the pattern starts at the top-left bit of the bit-plane, proceeds down through the next three bits in the bit-plane, and then continues at the next top-left bit and proceeds by making stripes of four bits until the width of the code-block is done. Once the end of the code-block is reached, the pattern starts with the next four bit stripe at the beginning of the code-block, as shown by FIG. 4. Thus, in FIG. 3, the scan pattern of the first bit-plane would be a1, b1, c1, d1, i1,j1, k1, l1, e1, f1, g1, h1, m1, n1, o1, p1.
This scan pattern is followed in each of the three coding passes. The decision as to in which pass a given bit is coded is made based on the “significance” of that bit's location and the significance of neighboring locations. A location is considered significant if a 1 has been coded for that location (quantized coefficient) in the current or previous bitplanes.
The first pass is called the significance propagation pass. A bit is coded in this pass if its location is not significant, but at least one of its eight-connected neighbors is significant. If a bit is coded in this pass, and the value of that bit is 1, its location is marked as significant for the purpose of coding subsequent bits in the current and subsequent bitplanes. Also, the sign bit is coded immediately after the 1 bit just coded.
The second pass is the magnitude refinement pass, where all bits from the locations that became significant in a previous bitplane are coded. The third and final pass is the clean-up pass, where bits not coded in the first two passes are taken care of. The result of these three scanning passes are the context vectors for the quantized coefficients.
At present, although hardware implementations of the JPEG2000 block encoder have been contemplated, a particular hardware implementation has not been devised. Several software implementations exist, such as JasPer (in C) and JJ2000 (in Java), but these are slow and CPU-intensive. Therefore, there is a need for hardware implementations of one or more of the various steps in the JPEG2000 encoding/decoding procedure.